10111. Tree Сумма левых листов

Дано бинарное дерево. Найдите сумму всех его левых листов.

Определение дерева:

//Java

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

left = null;

right = null;

}

}

// C++

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

Реализуйте функцию sumLeft которая возвращает сумму левых листов в дереве. Если заданное дерево не имеет левых листов, верните 0.

// Java

int sumLeft(TreeNode tree)

// C++

int sumLeft(TreeNode *tree)

Пример

Функция sumLeft возвращает 14 = 5 + 9.

РЕШЕНИЕ

дерево

Анализ алгоритма

Если tree = NULL, то сумма левых листов равна 0.

Если tree имеет левого сына, причем этот сын является листом (его левый и правый сын равны NULL), то возвращаем значение этого листа плюс сумма левых листов в поддереве tree → right.

Иначе возвращаем сумму левых листов в левом и правом поддереве.

Реализация алгоритма

int sumLeft(TreeNode *tree)

{

Если tree = NULL, то сумма левых листов равна 0.

if (tree == NULL) return 0;

Если tree имеет левого сына, причем этот сын является листом (его левый и правый сын равны NULL), то возвращаем значение этого листа плюс сумма левых листов в поддереве tree →right.

if (tree->left != NULL && tree->left->left == NULL && tree->left->right == NULL)

return tree->left->val + sumLeft(tree->right);

Иначе возвращаем сумму левых листов в левом и правом поддереве.

return sumLeft(tree->left) + sumLeft(tree->right);

}

Java реализация

int sumLeft(TreeNode tree)

{

if (tree == null) return 0;

if (tree.left != null && tree.left.left == null && tree.left.right == null)

return tree.left.val + sumLeft(tree.right);

return sumLeft(tree.left) + sumLeft(tree.right);

}